package com.huawei.M01.iterator.july;

import java.util.ArrayList;
import java.util.List;

/**
 * 功能：
 *
 * @author zhiwu
 * @Data 2023/7/13 1:22
 */
public class Combine {

    private static List<List<Integer>> ans;

    private static List<Integer> choose;

    private int n;

    private int k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;

        ans = new ArrayList<>();
        choose = new ArrayList<>();
        recurse(1);
        return ans;
    }

    private void recurse(int i) {
        // 剪枝
        if (choose.size() > k || choose.size() + n - i + 1 < k) {
            return;
        }
        if (i == n + 1) {
            ans.add(new ArrayList<>(choose));
            // 处理结果
            return;
        }
        recurse(i + 1);
        choose.add(i);
        recurse(i + 1);
        choose.remove(choose.size() - 1);
    }
}
